#include<bits/stdc++.h>

using namespace std;
using ll=long long;
const ll MOD = 10000;
ll e[2][2] = {1, 0, 0, 1};//单位矩阵

void add(ll a[2][2], ll b[2][2], ll c[2][2]) {

    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++) {
            c[i][j] = a[i][j] + b[i][j];
        }

}

void show(ll a[2][2]) {
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
}

void mul(ll a[2][2], ll b[2][2], ll c[2][2]) {
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++) {
            c[i][j] = 0;
            for (int k = 0; k < 2; k++) {
                c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD;
            }
        }

}

//矩阵快速幂
void power(ll a[2][2], int n, ll c[2][2]) {
    if (n == 0) {
        for (int i = 0; i < 2; i++)for (int j = 0; j < 2; j++)c[i][j] = e[i][j];
        return;
    }
    if (n == 1) {
        for (int i = 0; i < 2; i++)for (int j = 0; j < 2; j++)c[i][j] = a[i][j];
        return;
    }
    ll d[2][2];
    power(a, n / 2, d);
    if (n % 2 == 0) {
        mul(d, d, c);
    } else {
        mul(d, d, c);
        mul(c, a, d);
        power(d, 1, c);
    }

}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    ll a[2][2] = {1, 1, 1, 0};
    ll c[2][2] = {0, 0};
    int n;
    while (cin >> n) {
        if (n == -1)break;
        if (n <= 1)cout << n << endl;
        else {
            power(a, n - 1, c);
            cout << c[0][0] << endl;
        }

    }
}